class Point:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y


class Node:
    def __init__(self, pt, dist):
        self.pt = pt
        self.dist = dist


def has_exit(maze):
    ROW = len(maze)
    COL = len(maze[0])
    moves = [[0, -1], [0, 1], [1, 0], [-1, 0]]

    def isValid(x, y):
        return x > -1 and x < ROW and y > -1 and y < COL

    def isDest(x, y):
        return (x == 0 or x == ROW-1 or y == 0 or y == COL-1)
    rows = [x for x in maze if 'k' in x]
    if len(rows) > 1 or len(rows) == 0:
        # exist multiple Kates or no Kate
        raise 'muitlple Kates or no Kate'
    x0 = maze.index(rows[0])
    y0 = rows[0].index('k')
    st = Node(Point(x0, y0), 0)
    visited = [[False for i in range(COL)] for j in range(ROW)]
    visited[x0][y0] = True
    q = [st]
    while(q):
        curr = q.pop(0)
        if isDest(curr.pt.x, curr.pt.y):
            return True
        for mov in moves:
            row, col = curr.pt.x + mov[0], curr.pt.y + mov[1]
            if isValid(row, col) and not visited[row][col] and maze[row][col] == ' ':
                q.append(Node(Point(row, col), curr.dist+1))
                visited[row][col] = True
    return False
